/**
 * Creater with IntelliJ IDEA.
 * Description:
 * User: 86152
 * Dae: 2022-07-11
 * Time: 19:29
 */
public class puzzle {
    public static void main(String[] args) {
        puzzle puzzle = new puzzle();
        puzzle.sqrt(909520789);
    }
    public boolean judge (String str) {
        int len=str.length();
        int i=0;
        int j=len-1;
        for(int t=0;t<=len/2;t++) {
            if(str.charAt(i)!=str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    public int sqrt (int x) {
        int left=0;
        int right=x/2;
        if(x<1) {
            return 0;
        }
        if(x<4) return 1;
        while(left<=right) {
            int mid=left+(right-left)/2;
            if(mid==x/mid) {
                return mid;
            } else if(mid<x/mid) {
                if((mid+1)>x/(mid+1)) {
                    return mid;
                }
                left=mid+1;
            } else if(mid>x) {
                right=mid-1;
            }
        }
        return right;
    }
}
